package com.algrithom.quene;

import java.util.Deque;
import java.util.LinkedList;
import java.util.TreeSet;

/**
 * 53. 最大子序和
 * 
 * @author think
 */
public class Solution1 {
    
    public static void main(String[] args){
        //        int[] nums = new int[]{-2,1,-3,4,-1,2,1,-5,4,10,20,3,-10};
        //        int[] nums = new int[]{-2,-1};
        int[] nums = new int[]{-2,1};
        Solution1 comPro3 = new Solution1();
        long time = System.currentTimeMillis();
        System.out.println(comPro3.maxSubArray1(nums));
        System.out.println("Time is: " + (System.currentTimeMillis() - time));
        System.out.println(comPro3.maxSubArray2(nums));
        System.out.println("Time is: " + (System.currentTimeMillis() - time));
        System.out.println(comPro3.maxSubArray3(nums));
        System.out.println("Time is: " + (System.currentTimeMillis() - time));
        System.out.println(comPro3.maxSubArray4(nums));
        System.out.println("Time is: " + (System.currentTimeMillis() - time));
    }
    
    public int maxSubArray1(int[] nums){
        int len = nums.length;
        if (len == 1) {
            return nums[0];
        }
        int[] preSum = new int[len + 1];
        for (int i = 1; i <= len; i++) {
            preSum[i] = preSum[i - 1] + nums[i - 1];
        }
        int left = 0;
        int right = 1;
        int maxValue = Integer.MIN_VALUE;
        while (left < right && left < len) {
            while (right <= len) {
                maxValue = Math.max(preSum[right] - preSum[left],maxValue);
                right++;
            }
            left++;
            right = left + 1;
        }
        return maxValue;
    }
    
    public int maxSubArray2(int[] nums){
        int maxAns = nums[0];
        int[] sums = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            sums[i + 1] = Math.max(sums[i] + nums[i],nums[i]);
            maxAns = Math.max(maxAns,sums[i + 1]);
        }
        return maxAns;
    }
    
    public int maxSubArray3(int[] nums){
        Deque<Integer> deque = new LinkedList<>();
        int len = nums.length;
        int max = nums[0];
        int[] preSum = new int[len + 1];
        for (int i = 1; i <= len; i++) {
            preSum[i] = preSum[i - 1] + nums[i - 1];
        }
        for (int i = 0; i <= len; i++) {
            if (deque.isEmpty()) {
                deque.offer(i);
                continue;
            }
            max = Math.max(max,preSum[i] - preSum[deque.peekFirst()]);
            while (!deque.isEmpty() && preSum[deque.peekLast()] >= preSum[i]) {
                deque.pollLast();
            }
            deque.offer(i);
        }
        return max;
    }
    
    public int maxSubArray4(int[] nums){
        int ans = Integer.MIN_VALUE;
        TreeSet<Integer> sumSet = new TreeSet<>();
        int s = 0;
        sumSet.add(0);
        for (int v : nums) {
            s += v;
            Integer ceil = sumSet.ceiling(Integer.MIN_VALUE);
            if (ceil != null) {
                ans = Math.max(ans,s - ceil);
            }
            sumSet.add(s);
        }
        return ans;
    }
}
